package com.huangkailong.learning.datastructure.tree;

import com.huangkailong.learning.datastructure.common.Assert;
import com.huangkailong.learning.datastructure.tree.printer.BinaryTreeInfo;
import com.huangkailong.learning.datastructure.tree.printer.BinaryTrees;

import java.util.Objects;

/**
 * 二叉查找树
 *
 * @author huangkl
 * @since 1.0.0
 */
public class DefaultBinaryFindTree<K extends Comparable<K>, V> extends AbstractBinaryFindTree<K, V> {
    /**
     * 二叉查找树结点类型
     */
    private static class Node<K extends Comparable<K>, V> extends AbstractBinaryFindTree.Node<K,V>{
        /**
         * 左子树引用
         */
        Node<K,V> left;
        /**
         * 右子树引用
         */
        Node<K,V> right;

        public Node(K key, V value) {
            super(key, value);
        }

        @Override
        AbstractBinaryFindTree.Node<K, V> getLeft() {
            return left;
        }

        @Override
        AbstractBinaryFindTree.Node<K, V> getRight() {
            return right;
        }
    }

    private class ValueHolder{
        V value;
    }


    /**
     * 根结点
     */
    private Node<K,V> root;

    /**
     * 二叉查找树结点个数
     */
    private int size;


    /**
     * 添加一个键值对到二叉查找树
     *
     * @param key 二叉查找树结点键
     * @param value 二叉查找树结点值
     */
    @Override
    public V put(K key, V value){
        Assert.isNotNull(key, "Key 不能为空!");
        Assert.isNotNull(value, "Value 不能为空!");
        ValueHolder valueHolder = new ValueHolder();
        this.root = doPut(this.root, key, value, valueHolder);
        this.size++;
        return valueHolder.value;
    }

    private Node<K,V> doPut(Node<K, V> root, K key, V value, ValueHolder valueHolder){
        if(Objects.isNull(root)){
            return new Node<>(key, value);
        }
        if(lt(key, root.key)){
            root.left = doPut(root.left, key, value, new ValueHolder());
        }else if(gt(key, root.key)){
            root.right = doPut(root.right, key, value, new ValueHolder());
        }else {
            valueHolder.value = root.value;
            root.value = value;
        }
        return root;
    }

    /**
     * 删除指定 key 的结点
     *
     * @param key 二叉查找树结点键
     * @return 删除成功返回被删除的值，删除失败则返回 null
     */
    @Override
    public V delete(K key){
        Assert.isNotNull(key, "Key 不能为空!");
        if(isEmpty()){
            return null;
        }
        final ValueHolder valueHolder = new ValueHolder();
        this.root = doDelete(this.root, key , valueHolder);
        return valueHolder.value;
    }


    private Node<K,V> doDelete(Node<K,V> root, K key, ValueHolder valueHolder ){
        if(Objects.isNull(root)){
            return root;
        }

        if(lt(key, root.key)){
            root.left = doDelete(root.left, key, valueHolder);
            return root;
        }else if(gt(key, root.key)){
            root.right = doDelete(root.right, key, valueHolder);
            return root;
        }

        valueHolder.value = root.value;
        size--;
        if(Objects.nonNull(root.left) && Objects.nonNull(root.right)){
            // 有左子树和右子树
            handleHasLeftChildAndRightChild(root);
            return root;
        }else if(Objects.nonNull(root.left)){
            // 只有左子树
            return root.left;
        }else if(Objects.nonNull(root.right)){
            // 只有右子树
            return root.right;
        }
        // 叶子结点
        return null;
    }

    private void handleHasLeftChildAndRightChild(Node<K,V> root) {
        Node<K,V> p = root;
        Node<K,V> pp = null;
        while (Objects.nonNull(p.right)){
            pp = p;
            p = p.right;
        }
        root.key = p.key;
        root.value = p.value;
        pp.right = p.left;
    }

    /**
     * 获取二叉查找树结点个数
     *
     * @return 二叉查找树结点个数
     */
    @Override
    public int size(){
        return size;
    }

    @Override
    protected AbstractBinaryFindTree.Node<K, V> getRoot() {
        return this.root;
    }

    @Override
    public String printTree(BinaryTrees.PrintStyle printStyle) {
        return BinaryTrees.printString(new NodeInfo(this.root), printStyle);
    }

    private class NodeInfo implements BinaryTreeInfo{
        private Node root;

        public NodeInfo(Node root) {
            this.root = root;
        }

        @Override
        public Object root() {
            return root;
        }

        @Override
        public Object left(Object node) {
            return ((Node) node).left;
        }

        @Override
        public Object right(Object node) {
            return ((Node) node).right;
        }

        @Override
        public Object string(Object node) {
            return ((Node) node).key;
        }
    }
}
